home *** CD-ROM | disk | FTP | other *** search
/ Aminet 2 / Aminet AMIGA CDROM (1994)(Walnut Creek)[Feb 1994][W.O. 44790-1].iso / Aminet / comm / term / term34Source.lha / QuickSort.asm < prev    next >
Assembly Source File  |  1993-07-16  |  3KB  |  177 lines
  1. ***
  2. *
  3. *    A replacement for Lattice's qsort
  4. *
  5. *    This one is a stack miser and is (hopefully) faster.
  6. *
  7. *    The algorithm is taken from:
  8. *
  9. *    Stubbs, Webre, "Data Structures with Abstract
  10. *    Data Types and Pascal" (Pacific Grove: Brooks/Cole Pub. Co
  11. *    p. 256.
  12. *
  13. *    Modifications:
  14. *
  15. *    Middle element of array is used as partition element.
  16. *    Additional logic is provided for tail recursion optimization:
  17. *    Recursive calls sort arrays at most half the size of the array
  18. *    sorted during the previous recursive call -> little stack use.
  19. *
  20. ***
  21.  
  22.     csect    text,0,0,1,2
  23.  
  24.     XDEF    _qsort
  25.  
  26. _qsort:
  27.     movem.l D5/D4/D6/D7/A3,-(SP)
  28.     move.l    36(SP),A3
  29.     move.l    32(SP),D7
  30.     move.l    28(SP),D4    ; number of elements in array
  31.     move.l    24(SP),D5    ; bottom of array
  32.  
  33.     ; calculate size of array
  34.  
  35.     move.l    D4,D1        ; low word in right
  36.     swap    D1        ; high word in D1
  37.     mulu    D7,D4
  38.     mulu    D7,D1        ; multiply
  39.     swap    D1        ; shift high portion
  40.     clr.w    D1        ; mask high bits
  41.     add.l    D1,D4        ; add partials
  42.     sub.l    D7,D4        ; back up one
  43.     add.l    D5,D4        ; make into address
  44.  
  45.     ; calculate bit position to find middle
  46.  
  47.     moveq    #-1,D6
  48. cb0:
  49.     addq.l    #1,D6
  50.     btst    D6,D7
  51.     beq    cb0
  52.  
  53.     bsr    quick2
  54.  
  55.     movem.l (SP)+,D5/D4/D6/D7/A3
  56.     rts
  57.  
  58.     ;
  59.     ; exchange contents of A0, A1
  60.     ;
  61.  
  62. exch:
  63.     move.l    D7,D1
  64.     bra.s    ex1
  65. ex2:
  66.     move.b    (A0),D0
  67.     move.b    (A1),(A0)+
  68.     move.b    D0,(A1)+
  69. ex1:
  70.     dbra    D1,ex2
  71.     rts
  72.  
  73.     ; in: D5, right
  74.  
  75. quick2: movem.l D3/D2,-(SP)
  76.  
  77. quick2nr:
  78.     cmp.l    D5,D4
  79.     bls    q1        ; if left < right
  80.  
  81.     ; At this point, we wish to find middle of array
  82.     ; w/o multiplying or dividing.
  83.  
  84.     ; After finding size of array, in bytes,
  85.     ; we test hbit.     This bit will be set if we
  86.     ; are halfway between elements.
  87.  
  88.     move.l    D4,D1
  89.     sub.l    D5,D1        ; calculate size of array
  90.     btst    D6,D1
  91.     beq.s    q3
  92.     sub.l    D7,D1
  93. q3:
  94.     lsr.l    #1,D1        ; swap(d[left], d[mid]);
  95.     add.l    D5,D1
  96.  
  97.     move.l    D1,A0
  98.     move.l    D5,A1
  99.     bsr    exch
  100.  
  101.     move.l    D4,-(SP)
  102.     move.l    D5,-(SP)
  103.     jsr    (A3)
  104.     addq.l    #8,SP
  105.     tst.l    D0
  106.     ble.s    q2        ; if d[left] > d[right]
  107.  
  108.     move.l    D5,A0
  109.     move.l    D4,A1
  110.     bsr    exch        ; swap(d[left], d[right]);
  111. q2:
  112.     move.l    D5,D3        ; j := left
  113.     move.l    D4,D2        ; k := right
  114. q4:                ; repeat
  115.     add.l    D7,D3        ;  j := j + 1
  116.     move.l    D5,-(SP)
  117.     move.l    D3,-(SP)
  118.     jsr    (A3)
  119.     addq.l    #8,SP
  120.     tst.l    D0        ; until d[j] >= d[left]
  121.     blt    q4
  122. q5:
  123.     sub.l    D7,D2        ; k := k - 1
  124.     move.l    D5,-(SP)
  125.     move.l    D2,-(SP)
  126.     jsr    (A3)
  127.     addq.l    #8,SP
  128.     tst.l    D0        ; until d[k] <= d[left]
  129.     bgt    q5
  130.  
  131.     cmp.l    D3,D2
  132.     bls.s    q6        ; if j < k
  133.     move.l    D2,A1
  134.     move.l    D3,A0
  135.     bsr    exch        ; swap(d[j], d[k])
  136. q6:
  137.     cmp.l    D3,D2
  138.     bcc    q4        ; until j > k
  139.  
  140.     move.l    D2,A1
  141.     move.l    D5,A0
  142.     bsr    exch        ; swap(d[left], d[k])
  143.  
  144.     ; this is the recursive part.  Calculate sizes of
  145.     ; recursive calls to ensure smaller array is done
  146.     ; recursively and larger non-recursively.
  147.  
  148.     move.l    D2,D3
  149.     sub.l    D7,D2        ; k - 1
  150.     add.l    D7,D3        ; k + 1
  151.  
  152.     move.l    D2,D0
  153.     sub.l    D5,D0        ; (k - 1) - left
  154.     move.l    D4,D1
  155.     sub.l    D3,D1        ; right - (k + 1)
  156.     cmp.l    D0,D1
  157.     bge.s    q7
  158.  
  159.     move.l    D5,-(SP)
  160.     move.l    D3,D5
  161.     bsr    quick2        ; quick2(k + 1, right)
  162.     move.l    (SP)+,D5
  163.     move.l    D2,D4
  164.     bra    quick2nr    ; quick2(left, k - 1)
  165. q7:
  166.     move.l    D4,-(SP)
  167.     move.l    D2,D4
  168.     bsr    quick2        ; quick2(left, k - 1)
  169.     move.l    (SP)+,D4
  170.     move.l    D3,D5
  171.     bra    quick2nr    ; quick2(k + 1, right)
  172. q1:
  173.     movem.l (SP)+,D3/D2
  174.     rts
  175.  
  176.     END
  177.